/*
  leecode question 198

*/
#include "leecode.h"

class Solution {
  public:
    int rob(vector<int >& nums) {
      int count = nums.size();
      return robAt(nums, count);
      
    }

    int robAt(vector<int >& nums, int count) {
      auto iter = robbed.find(count);
      if( iter != robbed.end())
        return iter->second;
      if(count == 1) {
        robbed.insert({1, nums[0]});
        return nums[0];
      } else if(count == 2) {
        int ret = max(nums[0], nums[1]);
        robbed.insert({2, ret});
        return ret;
      }

      int ret1 = robAt(nums, count - 1);
      int ret2 = robAt(nums, count - 2) + nums[count - 1];
      int ret = max(robAt(nums, count - 1), robAt(nums, count - 2) + nums[count - 1]);
      robbed.insert({count, ret});
      return ret;
    }

    void expect(const vector<int>& nums, int expect) {
      int ret = rob(const_cast< vector<int>& >(nums));
      if(ret == expect) {
        cout << "rob success, expect:" << expect
             << ", result:" << ret << endl;
      } else {
        cout << "rob fail, expect:" << expect
             << ", result:" << ret << endl;
      }
    }

    unordered_map<int , int> robbed;
};

TEST(rob, robtest) {
  GTEST_SKIP();
  Solution().expect({2,7, 9, 3, 1}, 12);
}